package com.wp.targetOffer;

/**
 * Created by 王萍 on 2017/3/6 0006.
 */

/**
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 */
public class 二维数组中的查找 {

    public static void main(String[] args) {

        int[][] array = new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
//        int[][] array = new int[4][3];//表示4行3列   array.length为4，array[0].length为3

        System.out.println(array.length);
        System.out.println(array[0].length);
        int number = 6;

        System.out.println(find1(number, array));
        System.out.println(find2(number, array));
        System.out.println(find3(number, array));
        System.out.println(find4(number, array));

    }

    /**
     * 方法1，循环遍历
     *
     * @param target
     * @param array
     * @return
     */
    private static boolean find1(int target, int[][] array) {

        //行数
        int row = array.length;
        //列数
        int column = array[0].length;

        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (array[i][j] == target)
                    return true;
            }
        }
        return false;
    }


    /**
     * 方法2：由题可知，二维数组矩阵中上面的数字比下面的小，右边的比左边的大
     * 所以从左下方出发，如果目标数字更小，行数减1，如果大，列数加1.
     * 时间复杂度为O(row+column)
     *
     * @param target
     * @param array
     * @return
     */
    private static boolean find2(int target, int[][] array) {

        int row = array.length;
        int column = array[0].length;

        for (int i = row - 1, j = 0; i >= 0 && j < column; ) {
            if (target == array[i][j])
                return true;
            if (target < array[i][j]) {
                i--;
                continue;
            }
            if (target > array[i][j]) {
                j++;
                continue;
            }
            return false;
        }
        return false;
    }

    /**
     * 方法3：将每一行看做一个有序递增的数组，对每一行进行二分查找，然后遍历每一行
     * 时间复杂度为O(row*log(column))
     *
     * @param target
     * @param array
     * @return
     */
    private static boolean find3(int target, int[][] array) {

        int row = array.length;
        int column = array[0].length;

        for (int i = 0; i < row; i++) {
            int low = 0;
            int high = column - 1;
            while (low <= high) {
                int mid = (low + high) / 2;
                if (target > array[i][mid]) {
                    low = mid + 1;
                } else if (target < array[i][mid]) {
                    high = mid - 1;
                } else return true;
            }
        }

        return false;
    }

    /**
     * 方法4：将二维数组化为一维数组，在一维数组中遍历寻找
     * 方法简单，代码很少
     *
     * @param target
     * @param array
     * @return
     */
    private static boolean find4(int target, int[][] array) {

        for (int[] i : array) {
            for (int j : i) {
                if (j == target) return true;
            }
        }
        return false;
    }
}
